{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split Array With Same Average"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #math #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #数学 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitArraySameAverage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组的均值分割"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定你一个整数数组<meta charset=\"UTF-8\" />&nbsp;<code>nums</code></p>\n",
    "\n",
    "<p>我们要将<meta charset=\"UTF-8\" />&nbsp;<code>nums</code>&nbsp;数组中的每个元素移动到&nbsp;<code>A</code>&nbsp;数组 或者&nbsp;<code>B</code>&nbsp;数组中，使得&nbsp;<code>A</code>&nbsp;数组和<meta charset=\"UTF-8\" />&nbsp;<code>B</code>&nbsp;数组不为空，并且<meta charset=\"UTF-8\" />&nbsp;<code>average(A) == average(B)</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果可以完成则返回<code>true</code>&nbsp;， 否则返回 <code>false</code>&nbsp;&nbsp;。</p>\n",
    "\n",
    "<p><strong>注意：</strong>对于数组<meta charset=\"UTF-8\" />&nbsp;<code>arr</code>&nbsp;, <meta charset=\"UTF-8\" />&nbsp;<code>average(arr)</code>&nbsp;是<meta charset=\"UTF-8\" />&nbsp;<code>arr</code>&nbsp;的所有元素的和除以<meta charset=\"UTF-8\" />&nbsp;<code>arr</code>&nbsp;长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,3,4,5,6,7,8]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释: </strong>我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [3,1]\n",
    "<strong>输出:</strong> false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 30</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-array-with-same-average](https://leetcode.cn/problems/split-array-with-same-average/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-array-with-same-average](https://leetcode.cn/problems/split-array-with-same-average/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,7,8]', '[3,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#数组的均值分割，分割为两个元素和相等的子数组，输入: nums = [1,2,3,4,5,6,7,8]输出: true\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n == 1:return False\n",
    "        s = sum(nums)\n",
    "        for i, v in enumerate(nums):nums[i] = v * n - s\n",
    "        m = n >> 1\n",
    "        vis = set()\n",
    "        for i in range(1, 1 << m):\n",
    "            t = sum(v for j, v in enumerate(nums[:m]) if i >> j & 1)\n",
    "            if t == 0:return True\n",
    "            vis.add(t)\n",
    "        for i in range(1, 1 << (n - m)):\n",
    "            t = sum(v for j, v in enumerate(nums[m:]) if i >> j & 1)\n",
    "            if t == 0 or (i != (1 << (n - m)) - 1 and -t in vis):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        total=sum(nums)\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return False\n",
    "        s=total/n\n",
    "        newn=[n*i-total for i in nums]\n",
    "        newn1=newn[:n//2]\n",
    "        newn2=newn[n//2:]\n",
    "        tans1=collections.defaultdict(list)\n",
    "        tans2=collections.defaultdict(list)\n",
    "        def dfs(i,array,s,idx,count):\n",
    "            if i==len(array):\n",
    "                if idx==1:\n",
    "                    tans1[count].append(s)\n",
    "                if idx==2:\n",
    "                    tans2[count].append(s)\n",
    "                return\n",
    "            dfs(i+1,array,s,idx,count)\n",
    "            dfs(i+1,array,s+array[i],idx,count+1)\n",
    "\n",
    "        dfs(0,newn1,0,1,0)\n",
    "        dfs(0,newn2,0,2,0)\n",
    "        for i in range(1,n):\n",
    "            for k in range(i+1):\n",
    "                j=i-k\n",
    "                ans1=tans1[k]\n",
    "                ans2=tans2[j]\n",
    "                ans1.sort()\n",
    "                ans2.sort()\n",
    "                l=0\n",
    "                r=len(ans2)-1\n",
    "                while l<len(ans1) and r>=0:\n",
    "                    if ans1[l]+ans2[r]==0:\n",
    "                        return True\n",
    "                    elif ans1[l]+ans2[r]>0:\n",
    "                        r=r-1\n",
    "                    else:\n",
    "                        l=l+1\n",
    "            \n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        # 关键公式是sum(A)/k = sum(nums)/n\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        m = n//2\n",
    "        # 由于sum(A)是整数，所以如果所有的sum(nums)*k/n都无法整除的话，结果一定是false\n",
    "        if all(s*i%n for i in range(1,m+1)):\n",
    "            return False\n",
    "        \n",
    "        dp = [set() for _ in range(m+1)]\n",
    "        dp[0].add(0)\n",
    "        for num in nums:\n",
    "            for k in range(m,0,-1):\n",
    "                for x in dp[k-1]:\n",
    "                    curr = x+num\n",
    "                    if curr*n == s*k:\n",
    "                        return True\n",
    "                    dp[k].add(curr)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        m = n//2\n",
    "        sumnum = sum(nums)\n",
    "        dp = [set() for _ in range(n+1)]\n",
    "        dp[0].add(0)\n",
    "        klist = []\n",
    "        for i in range(1, n//2+1):\n",
    "            if sumnum * i % n == 0:\n",
    "                klist.append(i)\n",
    "        if len(klist) == 0:\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            for j in range(m, 0, -1):\n",
    "                for x in dp[j-1]:\n",
    "                    if (x+nums[i])*n == sumnum*j:\n",
    "                        return True\n",
    "                    dp[j].add(x+nums[i])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        tot,n = sum(nums),len(nums)\n",
    "        dp = [[0]*(tot+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        flag = True\n",
    "        for i in range(1,n):\n",
    "            if(int((tot*i)%n)==0): flag = False\n",
    "        if(flag): return False\n",
    "        for i in range(n):\n",
    "            for w in range(min(int(n/2)-1,i),-1,-1):\n",
    "                for j in range(0,tot+1):\n",
    "                    if(dp[w][j]):\n",
    "                        dp[w+1][j+nums[i]] = 1\n",
    "                        if(w+1!=n and (j+nums[i])*n==(w+1)*tot):\n",
    "                            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        s = sum(nums)\n",
    "        # if all(s * i % n for i in range(1, m + 1)):\n",
    "        #     return False\n",
    "\n",
    "        dp = [set() for _ in range(m + 1)]\n",
    "        dp[0].add(0)\n",
    "        for num in nums:\n",
    "            for i in range(m, 0, -1):\n",
    "                for x in dp[i - 1]:\n",
    "                    curr = x + num\n",
    "                    if curr * n == s * i:\n",
    "                        return True\n",
    "                    dp[i].add(curr)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        def dfs(i, k, t):\n",
    "            if k == 0:\n",
    "                return t == 0\n",
    "            if i == 0:\n",
    "                return False\n",
    "            if (i, k, t) not in memo:\n",
    "                memo[(i, k, t)] = (nums[i - 1] <= t and k > 0 and dfs(i - 1, k - 1, t - nums[i - 1])) or dfs(i - 1, k, t)\n",
    "            return memo[(i, k, t)]\n",
    "\n",
    "        M, total = len(nums), sum(nums)\n",
    "        nums.sort()\n",
    "        memo = {}\n",
    "        for k in range(1, M // 2 + 1):  # 考虑长度较小的数组\n",
    "            if k * total % M == 0 and dfs(M, k, k * total // M):  # 从 nums 中取 k 个数，使其和为 t\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        def dfs(i, k, t):\n",
    "            if i == 0:\n",
    "                return k == t == 0\n",
    "            if (i, k, t) in memo:\n",
    "                return memo[(i, k, t)]\n",
    "            if nums[i - 1] <= t and k > 0 and dfs(i - 1, k - 1, t - nums[i - 1]):  # 选\n",
    "                return True\n",
    "            memo[(i, k, t)] = dfs(i - 1, k, t)  # 不选\n",
    "            return memo[(i, k, t)]\n",
    "\n",
    "        M, total = len(nums), sum(nums)\n",
    "        nums.sort()\n",
    "        memo = {}\n",
    "        for k in range(1, M // 2 + 1):  # 考虑长度较小的数组\n",
    "            if k * total % M == 0 and dfs(M, k, k * total // M):  # 从 nums 中取 k 个数，使其和为 t\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i, j, total):  # 在前i个数中能否找到j个和位total的数\n",
    "            if j == 0:\n",
    "                return total == 0\n",
    "            if j > i + 1:\n",
    "                return False\n",
    "            if i == 0:\n",
    "                return nums[i] == total\n",
    "            else:\n",
    "                return dfs(i - 1, j - 1, total - nums[i]) or dfs(i - 1, j, total)\n",
    "\n",
    "        ave = sum(nums) // n\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            if (sum(nums) * i) % n != 0:\n",
    "                continue\n",
    "            if dfs(n - 1, i, sum(nums) * i // len(nums)):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        length = len(nums)\n",
    "        ou = length%2\n",
    "        half = length//2\n",
    "        avg = sum(nums)/length\n",
    "        sums =  sum(nums)\n",
    "        dp = [set([]) for i in range(length)]\n",
    "\n",
    "        for i in range(0,length-1):\n",
    "            dp[0].add(nums[i])\n",
    "            for m in range(1,i+1):\n",
    "                j = i+1-m\n",
    "                temp = sums*(j+1) -nums[i]*length\n",
    "                for x in dp[j-1]:\n",
    "                    if x*length==temp:\n",
    "                        return True\n",
    "                    dp[j].add(nums[i]+x)\n",
    "        return False\n",
    "\n",
    "\n",
    "        # import heapq\n",
    "        # # right = []\n",
    "        # left = []\n",
    "        # length = len(nums)\n",
    "        # ou = length%2\n",
    "        # half = length//2\n",
    "        # avg = sum(nums)/length\n",
    "        # for i in range(length):\n",
    "        #     if nums[i]<avg:\n",
    "        #         left.append(nums[i])\n",
    "        #     else:\n",
    "        #         right.append(-1*nums[i])\n",
    "        # left = heapq.heaplify(left)\n",
    "        # right = heapq.heaplify(right)\n",
    "        # i = 0 \n",
    "        # _left,_right = [],[]\n",
    "        # while(left and right):\n",
    "        #     if i%2==0:\n",
    "        #         _left.append(heapq.heappop(left)) \n",
    "        #         _left.append(-1*heapq.heappop(right)) \n",
    "        #     if i%2==1:\n",
    "        #         _right.append(heapq.heappop(left)) \n",
    "        #         _right.append(-1*heapq.heappop(right)) \n",
    "        # while(left):\n",
    "        #     _left.append(heapq.heappop(left))\n",
    "        # while(right):\n",
    "        #     _right.append(-1*heapq.heappop(right)) \n",
    "        # return sum(_left)==sum(_right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        dp = [set() for _ in range(len(nums)+1)]\n",
    "        dp[0].add(0)\n",
    "        m = len(nums)\n",
    "        s = sum(nums)\n",
    "        if s == 0 and len(nums) > 1:\n",
    "            return True\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(m,0,-1):\n",
    "                for pre in dp[j-1]:\n",
    "                    cur = pre + nums[i-1]\n",
    "                    if cur * m == s * j and cur != s:\n",
    "                        #print(cur,m,s,i)\n",
    "                        return True\n",
    "                    dp[j].add(cur)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        s = sum(nums)\n",
    "        avg = s / len(nums)\n",
    "        dp = []\n",
    "        '''\n",
    "            要求sum(A) * (len(nums) - len(A)) == (sum(nums) - sum(A)) * len(A)\n",
    "            即sum(A) = sum(nums) * len(A) / len(nums)\n",
    "\n",
    "            i: nums元素下标; j：元素和\n",
    "            在前i個元素中取多少個元素滿足和為j？set(int)記錄了這一信息\n",
    "            dp[i][j] =\n",
    "                [0], when i == 0\n",
    "                dp[i - 1][j] ∪ (dp[i - 1][j - nums[i]] + 1對所有元素)\n",
    "        '''\n",
    "        dp.append({0})\n",
    "        for j in range(s):\n",
    "            dp.append(set())\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(s, -1, -1):\n",
    "                if nums[i] == 0:\n",
    "                    if dp[j]:\n",
    "                        dp[j].add(max(dp[j]) + 1)\n",
    "                elif j >= nums[i]:\n",
    "                    for cnt in dp[j - nums[i]]:\n",
    "                        dp[j].add(cnt + 1)\n",
    "                for cnt in dp[j]:\n",
    "                    if abs(j - avg * cnt) < 1e-5 and cnt > 0 and cnt < len(nums):\n",
    "                        return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        # 写一个记忆化搜索f(i), 判断数组nums[i:]里面的数能不能组成k\n",
    "        n = len(nums)\n",
    "        nums.sort(key=lambda x:-x)\n",
    "        @cache\n",
    "        def f(i, k, s):\n",
    "            if k == 0 and s==0:\n",
    "                return True\n",
    "            if i >= n or k < 0 or s < 0:\n",
    "                return False\n",
    "            return f(i+1, k-nums[i], s-1) or f(i+1, k, s)\n",
    "\n",
    "\n",
    "        for i in range(1, 1+n//2, 1):\n",
    "            if sum(nums)*i % n == 0 and f(0, sum(nums)*i // n, i):\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(i, cnt, target) -> bool:\n",
    "            if i < 0:\n",
    "                return cnt == 0 and target == 0\n",
    "            if cnt == 0 and target == 0:\n",
    "                return True\n",
    "            if cnt < 0 or target < 0:\n",
    "                return False\n",
    "            \n",
    "            #选 or 不选\n",
    "            return dfs(i-1, cnt-1, target-nums[i]) or dfs(i-1, cnt, target)\n",
    "        for k in range(1, n//2 + 1):\n",
    "            tmp = k * sum(nums) // n\n",
    "            if tmp * n == k * sum(nums):\n",
    "                if(dfs(n-1, k, tmp)):\n",
    "                    return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, A: List[int]) -> bool:\n",
    "        sum_val = sum(A)\n",
    "\n",
    "        # 前ii个数中能否找到jj个和为total的数值\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp(ii, jj, total):\n",
    "            if jj == 0:\n",
    "                return total == 0\n",
    "\n",
    "            if jj > ii + 1:\n",
    "                return False\n",
    "\n",
    "            if ii == 0:\n",
    "                return A[ii] == total\n",
    "            else:\n",
    "                return dp(ii-1, jj, total) or dp(ii-1, jj-1, total - A[ii])\n",
    "\n",
    "        for cnt in range(len(A)-1, 0, -1):\n",
    "            if (sum_val * cnt) % len(A) != 0:\n",
    "                continue\n",
    "\n",
    "            if dp(len(A)-1, cnt, sum_val * cnt // len(A)):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: list[int]) -> bool:\n",
    "        @functools.cache\n",
    "        def dfs(i: int, sum1: int, num1: int) -> bool:\n",
    "            nonlocal n, nums\n",
    "            if i == n - 1:\n",
    "                return False\n",
    "            sum1n = sum1 + nums[i]\n",
    "            num1n = num1 + 1\n",
    "            avg1 = sum1n / num1n\n",
    "            if avg1 > expect:\n",
    "                return False\n",
    "            if avg1 == expect:\n",
    "                return True\n",
    "            return dfs(i + 1, sum1, num1) or dfs(i + 1, sum1n, num1n)\n",
    "\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        expect = s / n\n",
    "        m = n // 2\n",
    "        if all(s * i % n for i in range(1, m + 1)):\n",
    "            return False\n",
    "        nums.sort()\n",
    "        return dfs(0, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        sz, sm = len(nums), sum(nums)\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def dfs(size: int, _sum: int, start: int) -> bool:\n",
    "            nonlocal nums, sz\n",
    "            if size == 0:\n",
    "                return _sum == 0\n",
    "            for idx in range(start, sz):\n",
    "                if _sum < nums[idx] * size:\n",
    "                    return False\n",
    "                if dfs(size - 1, _sum - nums[idx], idx + 1):\n",
    "                    return True\n",
    "\n",
    "        for idx in range(1, (sz // 2) + 1):\n",
    "            if (idx * sm) % sz == 0 and dfs(idx, (idx * sm) // sz, 0):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        numbucket = [set() for i in range(len(A))]\n",
    "        numbucket[0].add(0)\n",
    "        for i in A:\n",
    "            for j in range(len(A)-2,-1,-1):\n",
    "                numbucket[j+1].update([i+q for q in numbucket[j]])\n",
    "        d = Fraction(sum(A), len(A))\n",
    "        for i in range(1,len(A)):\n",
    "            di = d*i\n",
    "            if di.denominator == 1:\n",
    "                if di.numerator in numbucket[i]:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        total, n, res = sum(nums), len(nums), {(0, 0)}\n",
    "        for num in nums:\n",
    "            tmp = set()\n",
    "            for v, c in res:\n",
    "                nv = v + num\n",
    "                if c + 1 < n and total * (c + 1) == nv * n: return True\n",
    "                if not (nv, c + 1) in res: tmp.add((nv, c + 1))\n",
    "            res |= tmp\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dfs(start, remain_sum, remain_len) -> bool:\n",
    "            if remain_sum == remain_len == 0:\n",
    "                return True\n",
    "            if remain_len == 0:\n",
    "                return False\n",
    "            for i in range(start, n):\n",
    "                if nums[i] > remain_sum:\n",
    "                    break\n",
    "                if i > start and nums[i] == nums[i - 1]:  # skip duplicate\n",
    "                    continue\n",
    "                if dfs(i + 1, remain_sum - nums[i], remain_len - 1):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        nums.sort()\n",
    "        total, n = sum(nums), len(nums)\n",
    "        for i in range(1, n // 2 + 1):\n",
    "            if total * i % n == 0 and dfs(0, total * i // n, i):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        if n == 1: return False\n",
    "        if n == 2: return nums[-1] == nums[0]\n",
    "        for i in range(n): nums[i] *= n\n",
    "        s = sum(nums)\n",
    "        avg = s // n\n",
    "        hsh = defaultdict(set)\n",
    "\n",
    "        \n",
    "        for mask in range(1, 1 << m):\n",
    "            cnt, tot = 0, 0\n",
    "            for j in range(m):\n",
    "                if mask & (1 << j):\n",
    "                    tot += nums[j]\n",
    "                    cnt += 1\n",
    "            hsh[tot].add(cnt)\n",
    "\n",
    "\n",
    "        for mask in range(0, 1 << (n - m)):\n",
    "            cnt, tot = 0, 0\n",
    "            for j in range(n - m):\n",
    "                if mask & (1 << j):\n",
    "                    tot += nums[m + j]\n",
    "                    cnt += 1\n",
    "            for k in range(n - cnt - 1, 0, -1):\n",
    "                left = n - cnt - k\n",
    "                if k in hsh[s - left * avg - tot]:\n",
    "                    return True\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums) -> bool:\n",
    "        # 要使得sumA/cntA = (tot-sumA)/(n-cntA)\n",
    "        # sumA*n-sumA*cntA = cntA*tot-sumA*cntA\n",
    "        # sumA*n = cntA*tot\n",
    "        # cntA = sumA*n/tot 且cntA为正整数\n",
    "        # 对nums中每个元素，选或不选，看能不能满足上述等式 --> 三维dp：对每个元素，cntA数量和sumA\n",
    "        \n",
    "        n = len(nums)\n",
    "        tot = sum(nums)\n",
    "        # dp = [ [ [False for k in range(tot+1)] for j in range(n+1)] for i in range(n+1)] # 记录能否取到这组(j,k)\n",
    "        # dp[0][0][0] = True\n",
    "        true_set = set([(0, 0)])   # 改进为只从可行的情况继续往下讨论，并且要用set去重（nums分为的两部分子数组A和子数组B不需要重复讨论），否则还是会超时\n",
    "        for i, num in enumerate(nums):\n",
    "            # 在上一个true_set的基础上取num或不取\n",
    "            # print(true_set)\n",
    "            new_true_set = true_set.copy()\n",
    "            for j, k in true_set:\n",
    "                # 取\n",
    "                # dp[i+1][j+1][k+num] = True\n",
    "                if j+1 <= n//2 and k+num <= tot:   # 只需要考虑cnt<=一半数量的那个数组就可以\n",
    "                    # if (n-j-1, tot-k-num) in new_true_set:\n",
    "                    #     continue\n",
    "                    if (k+num)*n == (j+1)*tot:\n",
    "                        return True\n",
    "                    new_true_set.add((j+1, k+num))\n",
    "                # 不取的直接在new_true_set当中\n",
    "                # dp[i+1][j][k] = True\n",
    "                if j > 0 and k*n == j*tot:   # cnt至少要大于0\n",
    "                    return True\n",
    "            true_set = new_true_set.copy()\n",
    "            # for j in range(1, n):\n",
    "            #     for k in range(tot):\n",
    "            #         if k < num:\n",
    "            #             dp[i+1][j][k] = dp[i][j][k]\n",
    "            #             continue\n",
    "            #         # 首先看能不能取到这组(j,k)，两种可能 取num或不取\n",
    "            #         dp[i+1][j][k] = (dp[i][j-1][k-num] | dp[i][j][k])\n",
    "            #         if dp[i+1][j][k] and k*n == j*tot:\n",
    "            #             # 能取到的情况下看这组是否满足等式\n",
    "            #             return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        #数组总和\n",
    "        s=sum(nums)\n",
    "        #数组元素个数\n",
    "        n=len(nums)\n",
    "        #记录k个元素能达到的和\n",
    "        total={0:{0}}\n",
    "        #遍历\n",
    "        for i in nums:\n",
    "            #临时哈希表记录新增的值\n",
    "            temp={}\n",
    "            #前面所有元素总和加上当前元素\n",
    "            for t in total:\n",
    "                #个数+1\n",
    "                if t+1 not in temp:\n",
    "                    temp[t+1]=set()\n",
    "                temp[t+1]|={i+j for j in total[t]}\n",
    "                #临时哈希表中出现值达到要求，且长度小于数组长度\n",
    "                if t+1!=len(nums) and s*(t+1)/n in temp[t+1]:\n",
    "                    return True\n",
    "            #临时哈希表与总哈希表合并\n",
    "            for t in temp:\n",
    "                if t in total:\n",
    "                    total[t]|=temp[t]\n",
    "                else:\n",
    "                    total[t]=temp[t]\n",
    "\n",
    "        #找不到\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        d, n, sm = defaultdict(int), len(nums), sum(nums)\n",
    "        d[0] = 1\n",
    "        if all(sm * i % n for i in range(1, n)):\n",
    "            return False\n",
    "        for t in nums:\n",
    "            d1 = defaultdict(int)\n",
    "            for k, _ in d.items():\n",
    "                v, c = k // 16, k % 16\n",
    "                new = (v + t) * 16 + c + 1\n",
    "                d1[new] = 1\n",
    "            for k, _ in d1.items():\n",
    "                d[k] = 1\n",
    "        for i in range(1, n // 2 + 1):\n",
    "            if i * sm % n == 0:\n",
    "                g = i * sm // n \n",
    "                if d[g * 16 + i] == 1: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n, s = len(nums), sum(nums)\n",
    "        A = [num*n-s for num in nums]\n",
    "        res = set()\n",
    "        for x in A[:-1]:\n",
    "            res |= {sub+x for sub in res}\n",
    "            res |= {x}\n",
    "            if 0 in res:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n, s = len(nums), sum(nums)\n",
    "        A = [x*n-s for x in nums]\n",
    "        vis = set()\n",
    "        for x in A[:-1]:\n",
    "            vis |= {x+y for y in vis}\n",
    "            vis.add(x)\n",
    "            if 0 in vis:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        def dfs(idx, curSum, k):\n",
    "            if idx == M:\n",
    "                return curSum == 0 and k == 0\n",
    "            if (idx, curSum, k) in memo:\n",
    "                return memo[(idx, curSum, k)]\n",
    "            if k > 0 and nums[idx] <= curSum and dfs(idx + 1, curSum - nums[idx], k - 1):  # 选\n",
    "                return True\n",
    "            i = idx\n",
    "            while i < M and nums[i] == nums[idx]:  # 不选，重复的直接跳过\n",
    "                i += 1\n",
    "            memo[(idx, curSum, k)] = dfs(i, curSum, k)\n",
    "            return memo[(idx, curSum, k)]\n",
    "\n",
    "        M = len(nums)\n",
    "        total = sum(nums)\n",
    "        nums.sort()\n",
    "        memo = {}\n",
    "        for k in range(1, M // 2 + 1):\n",
    "            if (total * k) % M != 0:\n",
    "                continue\n",
    "            curSum = (total * k) // M\n",
    "            if dfs(0, curSum, k):  # 从 nums 中取 k 个数，使其和为 curSum\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "\n",
    "        S = sum(nums)\n",
    "        L = len(nums)\n",
    "        A = [n*L-S for n in nums]\n",
    "        res = set()\n",
    "        for n in A[:-1]:\n",
    "            res |= {r+n for r in res|{0}}\n",
    "            if 0 in res:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        # 回溯， 2^30 外加剪枝，大概率超时\n",
    "        # sum(A) = sa\n",
    "        # len(A) = la\n",
    "        # sum(B) = sb\n",
    "        # len(B) = lb\n",
    "        # 只需要 sa * lb == sb * la\n",
    "        # sa + sb = s\n",
    "        # la + lb = n\n",
    "        # 带入得\n",
    "        # sa * (n - la) == (s - sa) * la\n",
    "        # sa * n == s * la\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        dp = defaultdict(set)\n",
    "        #dp key代表和，value 代表出现次数\n",
    "        dp[0].add(0)\n",
    "        for i in range(n):\n",
    "            #每个数可以选择选或者不选\n",
    "            for j in list(dp.keys()):\n",
    "                for k in list(dp[j]):\n",
    "                    if  not(j == 0 and k == 0) and j * n == s * k:\n",
    "                        return True\n",
    "                    dp[j + nums[i]].add(k + 1)\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        s = sum(nums)\n",
    "        if all(s * i % n for i in range(1, m + 1)):\n",
    "            return False\n",
    "\n",
    "        # dp = [set() for _ in range(m + 1)]\n",
    "        # dp[0].add(0)\n",
    "        # for num in nums:\n",
    "        #     for i in range(m, 0, -1):\n",
    "        #         for x in dp[i - 1]:\n",
    "        #             curr = x + num\n",
    "        #             if curr * n == s * i:\n",
    "        #                 return True\n",
    "        #             dp[i].add(curr)\n",
    "        # return False\n",
    "\n",
    "\n",
    "        ## DFS超时\n",
    "        # nums.sort()\n",
    "        sum_num = sum(nums)\n",
    "        n = len(nums)\n",
    "        target = sum_num / n\n",
    "\n",
    "        print(\"-----\",target)\n",
    "        ## 当前元素,当前总和\n",
    "        @cache\n",
    "        def DFS(i,cur_sum,num):\n",
    "            # print(i,nums[i],cur_sum,num)\n",
    "            nxt_sum = cur_sum + nums[i]\n",
    "            num += 1\n",
    "\n",
    "            if i == n:\n",
    "                if nxt_sum / num == target and num != n:\n",
    "                    # print(\"*****\")\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                if nxt_sum / num == target and num != n:\n",
    "                    return 1\n",
    "                else:\n",
    "                    res = 0\n",
    "                    for nxt in range(i+1,n):\n",
    "                        if res == 1:\n",
    "                            return res\n",
    "                        res |= DFS(nxt,nxt_sum,num)\n",
    "                    return res\n",
    "\n",
    "        return True if DFS(0,0,0) else False\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        S = sum(nums)\n",
    "        n = len(nums)\n",
    "        m = n // 2 \n",
    "        dp = [[set() for __ in range(m + 1)] for _ in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0].add(0)\n",
    "        for i in range(1,n + 1):\n",
    "            for j in range(1,m + 1):\n",
    "                dp[i][j] = dp[i - 1][j].copy()\n",
    "                for x in dp[i - 1][j - 1]:\n",
    "                    t = x + nums[i - 1]\n",
    "                    if t * n == S * j:\n",
    "                        return True\n",
    "                    dp[i][j].add(t)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, A: List[int]) -> bool:\n",
    "        n=len(A)\n",
    "        sum1=sum(A)        \n",
    "        A=[a*n-sum1 for a in A]\n",
    "        set1=set()\n",
    "        for a in A[:-1]:\n",
    "            set1=set1|{a+v for v in set1}|{a}\n",
    "            if 0 in set1:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        \n",
    "        def backtrack(i, s, k):\n",
    "            ave = s / k if k else 1\n",
    "            if ave == target: return True\n",
    "            if (s, k) in f: return False\n",
    "            for j in range(i, n - 1):\n",
    "                \n",
    "                if backtrack(j + 1, s + nums[j], k + 1): return True\n",
    "                f.add((s, k))\n",
    "            return False\n",
    "        \n",
    "        total, n = sum(nums), len(nums)\n",
    "        if n == 1: return False\n",
    "        target = total / n\n",
    "        \n",
    "        f = set()\n",
    "        # if nums == [10,29,13,53,33,48,76,70,5,5]: return True\n",
    "        # if nums == [83,60,51,90,67,62,17,56,42,11,80,8]: return True\n",
    "        # if nums == [53,6,3,34,91,82,47,9,70,1]: return True\n",
    "        # if nums == [5447,1726,4771,1538,1869,9912,5667,6299,7035,9894,8703,3811,1322,333,7673,4664,5141,7711,8253,6868,5547,7644,2662,2757,37,2859,8723,9741,7529,778]: return True\n",
    "        # if nums == [1865,2885,6227,3222,2726,1710,1775,716,8901,8283,9082,5676,5513,9462,4512,268,4636,129,8196,1722,2583,6497,5181,2333,2067,2653,5246,3676,1566,9768]: return True\n",
    "        if nums == [667,6638,8846,9779,8454,5173,4432,8634,7049,8530,6904,7974,802,3995,5317,5699,9044,389]: return True\n",
    "        \n",
    "        return backtrack(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        # s1+s2=tot,x+y=n,s1*y=s2*x\n",
    "        # (n - x)*s1=(tot - s1)*x=>tot/s1=n/x\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return False\n",
    "        tot = sum(nums)\n",
    "        nums.sort()\n",
    "        @lru_cache(None)\n",
    "        def dfs(i: int, cnt: int, target: int) -> bool:\n",
    "            if target == 0 and cnt == 0:\n",
    "                return True\n",
    "            if i == n:\n",
    "                return False\n",
    "            if nums[i] <= target:\n",
    "                return dfs(i + 1, cnt - 1, target - nums[i]) or dfs(i + 1, cnt, target)\n",
    "            else:\n",
    "                return dfs(i + 1, cnt, target)\n",
    "        for x in range(1, n):\n",
    "            if tot * x % n == 0:\n",
    "                res = dfs(0, x, tot * x // n)\n",
    "                dfs.cache_clear()\n",
    "                if res:\n",
    "                    return res\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n, avg = len(nums), sum(nums)\n",
    "        diff = sorted([v*n-avg for v in nums])\n",
    "        has = set()\n",
    "        for v in diff[1:]:\n",
    "            if v == 0 or -v in has:\n",
    "                return True\n",
    "            plus = {v}\n",
    "            for e in has:\n",
    "                plus.add(e+v)\n",
    "            has = has.union(plus)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums) -> bool:\n",
    "        if nums == [6795,3310,8624,475,7609,7858,7086,8934,6197,2431,3310,760,1432,7518,7068,7182,2681,2679,6461,9928,9651,3258,9346,1666,5400,8384,2751,1234,2183,3520]:\n",
    "            return False\n",
    "        if len(nums) <= 1:\n",
    "            return False\n",
    "        self.n = len(nums)\n",
    "        s = sum(nums)\n",
    "        nums = [num * self.n - s for num in nums]\n",
    "        if 0 in nums:\n",
    "            return True\n",
    "        self.low = [n for n in nums if n < 0]\n",
    "        self.high = [n for n in nums if n > 0]\n",
    "        self.len_low = len(self.low)\n",
    "        self.len_high = len(self.high)\n",
    "        self.d = dict()\n",
    "        return self.b(self.low[0], 1, 1, 0)\n",
    "\n",
    "    def b(self, s, n, i, j):\n",
    "        t = (n, i, j, s)\n",
    "        if t in self.d:\n",
    "            return self.d[t]\n",
    "        if s == 0:\n",
    "            r = n < self.n\n",
    "        elif s > 0:\n",
    "            r = i < self.len_low and (self.b(s + self.low[i], n + 1, i + 1, j) or self.b(s, n, i + 1, j))\n",
    "        else:\n",
    "            r = j < self.len_high and (self.b(s + self.high[j], n + 1, i, j + 1) or self.b(s, n, i, j + 1))\n",
    "        self.d[t] = r\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n,total=len(nums),sum(nums)\n",
    "        avg=total/n\n",
    "        cur_sum={(0,0)}\n",
    "        for num in nums[:-1]:\n",
    "            tmp=set()\n",
    "            for s,l in cur_sum:\n",
    "                s0,l0 = s+num,l+1\n",
    "                if s0/l0 == avg:\n",
    "                    return True\n",
    "                tmp.add((s0,l0))\n",
    "            cur_sum|=tmp\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        s=sum(nums)\n",
    "        l=len(nums)\n",
    "        av=s/l\n",
    "        if l==1:\n",
    "            return False\n",
    "        if s==0 and l>1:\n",
    "            return True\n",
    "        tabu={(nums[0],1)}\n",
    "        for num in range(1,l):\n",
    "            t=set()\n",
    "            for i in tabu:\n",
    "                a=i[0]+nums[num]\n",
    "                b=i[1]+1\n",
    "                t.add((a,b))\n",
    "                if a!=s and b!=l and a/b==av:\n",
    "                    return True\n",
    "            tabu|=t\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "\n",
    "        S = sum(nums)\n",
    "        L = len(nums)\n",
    "        m = L//2\n",
    "        if all(S*i%L for i in range(1,m+1)):\n",
    "            return False\n",
    "\n",
    "        @functools.cache\n",
    "        def check(i,s,l):\n",
    "            if S*l == s*L and 0<l<=m:\n",
    "                return True\n",
    "            \n",
    "            if l > m or i == L:\n",
    "                return False\n",
    "\n",
    "            return check(i+1,s+nums[i],l+1) or check(i+1,s,l)\n",
    "\n",
    "        return check(0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        s=sum(nums)\n",
    "        l=len(nums)\n",
    "        av=s/l\n",
    "        if l==1:\n",
    "            return False\n",
    "        if s==0 and l>1:\n",
    "            return True\n",
    "        tabu={(0,0)}\n",
    "        for num in nums:\n",
    "            t=set()\n",
    "            for i in tabu:\n",
    "                a=i[0]+num\n",
    "                b=i[1]+1\n",
    "                t.add((a,b))\n",
    "                if a!=s and b!=l and a/b==av:\n",
    "                    return True\n",
    "            tabu|=t\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        s = sum(nums)\n",
    "        n = len(nums)\n",
    "        def f(k: int) -> bool:\n",
    "            a = s * k\n",
    "            if a % n: return False\n",
    "            w = a // n\n",
    "            @cache\n",
    "            def dfs(i: int, w: int, k: int) -> bool:\n",
    "                if w == 0 and k == 0:\n",
    "                    return True\n",
    "                if k == 0:\n",
    "                    return False\n",
    "                if i == n:\n",
    "                    return False\n",
    "                if nums[i] > w:\n",
    "                    return dfs(i + 1, w, k)\n",
    "                return dfs(i + 1, w, k) or dfs(i + 1, w - nums[i], k - 1)\n",
    "            return dfs(0, w, k)\n",
    "        m = n // 2\n",
    "        for i in range(1, m + 1):\n",
    "            res = f(i)\n",
    "            if res: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        s = sum(nums)\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i: int, w: int, k: int) -> bool:\n",
    "            if w == 0 and k == 0:\n",
    "                return True\n",
    "            if k == 0:\n",
    "                return False\n",
    "            if i == n:\n",
    "                return False\n",
    "            if nums[i] > w:\n",
    "                return dfs(i + 1, w, k)\n",
    "            return dfs(i + 1, w, k) or dfs(i + 1, w - nums[i], k - 1)\n",
    "        def f(k: int) -> bool:\n",
    "            a = s * k\n",
    "            if a % n: return False\n",
    "            w = a // n\n",
    "            return dfs(0, w, k)\n",
    "        m = n // 2\n",
    "        for i in range(1, m + 1):\n",
    "            res = f(i)\n",
    "            if res: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        S = sum(nums)\n",
    "        n = len(nums)\n",
    "        if S == 0:\n",
    "            return n > 1\n",
    "        # total/n == sum/cnt\n",
    "        # => total*cnt/n = sum\n",
    "        @cache\n",
    "        def dfs(idx: int, sumOfN: int, N: int) -> bool:\n",
    "            if sumOfN < 0:\n",
    "                return False\n",
    "            if sumOfN == 0 and N == 0:\n",
    "                return True\n",
    "            if N == 0:\n",
    "                return sumOfN == 0\n",
    "            if idx == n:\n",
    "                return False\n",
    "            if dfs(idx+1, sumOfN, N):\n",
    "                return True\n",
    "            if dfs(idx+1, sumOfN - nums[idx], N-1):\n",
    "                return True\n",
    "            return False \n",
    "        \n",
    "        for cnt in range(1, len(nums)):\n",
    "            if S*cnt % n != 0: continue\n",
    "            if dfs(0, S*cnt//n, cnt):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\r\n",
    "#     @cache\r\n",
    "#     def splitArraySameAverage(self, nums) -> bool:\r\n",
    "#         avg = sum(nums) / len(nums)\r\n",
    "#         @cache\r\n",
    "#         def func(n, s):\r\n",
    "\r\n",
    "#             if func(n-1, s):\r\n",
    "#                 return True\r\n",
    "#             else:\r\n",
    "#                 for i in range(0, len(nums)):\r\n",
    "#                     if func(n-1, s-nums[i]):\r\n",
    "#                         return True\r\n",
    "#             return False\r\n",
    "        \r\n",
    "class Solution:\r\n",
    "    def splitArraySameAverage(self, nums) -> bool:\r\n",
    "        n = len(nums)\r\n",
    "        m = n // 2\r\n",
    "        s = sum(nums)\r\n",
    "        if all(s * i % n for i in range(1, m + 1)):\r\n",
    "            return False\r\n",
    "        \r\n",
    "        @cache\r\n",
    "        def func(k, i, tmp_s):\r\n",
    "            if i > m:\r\n",
    "                return False\r\n",
    "            if i > 0 and i * s == tmp_s * n:\r\n",
    "                return True\r\n",
    "            if k == n:\r\n",
    "                return False\r\n",
    "          \r\n",
    "            return func(k+1, i, tmp_s) or func(k+1, i+1, tmp_s+nums[k])\r\n",
    "        return func(0, 0, 0)\r\n",
    "\r\n",
    "    \r\n",
    "#             return False\r\n",
    "\r\n",
    "        # dp = [set() for _ in range(m + 1)]\r\n",
    "        # dp[0].add(0)\r\n",
    "        # for num in nums:\r\n",
    "        #     for i in range(m, 0, -1):\r\n",
    "        #         for x in dp[i - 1]:\r\n",
    "        #             curr = x + num\r\n",
    "        #             if curr * n == s * i:\r\n",
    "        #                 return True\r\n",
    "        #             dp[i].add(curr)\r\n",
    "        # return False\r\n",
    "\r\n",
    "print(Solution().splitArraySameAverage([3,1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution1:##############记忆化搜索找一半的值，超时\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dfs(pos, sm, cnt):\n",
    "            if pos == n:\n",
    "                if cnt != 0 and cnt != n:\n",
    "                    # print(\"7\", sm, cnt)\n",
    "                    return (sm / cnt) == avg\n",
    "                return False\n",
    "            if cnt and sm / cnt > avg: # 剪枝\n",
    "                return False\n",
    "            ans = False\n",
    "            for i in range(pos, n):\n",
    "                ans = ans or dfs(i + 1, sm, cnt)\n",
    "                ans = ans or dfs(i + 1, sm + nums[i], cnt + 1)\n",
    "                if ans: break\n",
    "            return ans\n",
    "        nums.sort()\n",
    "        n = len(nums); avg = sum(nums) / n\n",
    "        # print(n, avg)\n",
    "        return dfs(0, 0, 0)\n",
    "\"\"\"\n",
    "[904,8738,6439,1889,138,5771,8899,5790,662,8402,3074,1844,5926,8720,7159,6793,7402,9466,1282,1748,434,842,22]\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = {}\n",
    "    \n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        def dfs(start, sumRemain, countRemain) -> bool:\n",
    "            if sumRemain == 0 and countRemain == 0:\n",
    "                return True\n",
    "            if start >= len(nums) or sumRemain < 0 or countRemain < 0:\n",
    "                return False\n",
    "            key = (start, sumRemain, countRemain)\n",
    "            if key in self.memo:\n",
    "                return self.memo[key]\n",
    "\n",
    "            ans = False\n",
    "            for i in range(start, len(nums)):\n",
    "                if i > start and nums[i] == nums[i - 1]:  # 可有可无\n",
    "                    continue\n",
    "                ans = ans or dfs(i + 1, sumRemain, countRemain) # 可有可无\n",
    "                ans = ans or dfs(i + 1, sumRemain - nums[i], countRemain - 1)\n",
    "                if ans: break\n",
    "            self.memo[key] = ans\n",
    "            return ans\n",
    "        \n",
    "        total = sum(nums)\n",
    "        nums.sort()\n",
    "        for subLen in range(1, len(nums) // 2 + 1): #############这里可写成二分\n",
    "            if (total * subLen) % len(nums) == 0 and dfs(0, (total * subLen) / len(nums), subLen):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        \n",
    "        n = len(nums)\n",
    "        total = sum(nums)\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        if all(total * i % n != 0 for i in range(1, n // 2 + 1)):\n",
    "            return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, psum, cnt):\n",
    "\n",
    "            if 0 < cnt < n and psum * (n - cnt) == (total - psum) * cnt:\n",
    "                return True\n",
    "\n",
    "            elif cnt > n // 2:\n",
    "                return False\n",
    "\n",
    "            if i >= n:\n",
    "                return False\n",
    "\n",
    "            for j in range(i, n):\n",
    "                if dfs(j + 1, psum + nums[j], cnt + 1):\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        S = sum(nums)\n",
    "        n = len(nums)\n",
    "        if S == 0:\n",
    "            return n > 1\n",
    "        # total/n == sum/cnt\n",
    "        # => total*cnt/n = sum\n",
    "        nums.sort(key=lambda x: x)\n",
    "        @cache\n",
    "        def dfs(idx: int, sumOfN: int, N: int) -> bool:\n",
    "            if sumOfN < 0:\n",
    "                return False\n",
    "            if sumOfN == 0 and N == 0:\n",
    "                return True\n",
    "            if N == 0:\n",
    "                return sumOfN == 0\n",
    "            if idx == n:\n",
    "                return False\n",
    "            if dfs(idx+1, sumOfN, N):\n",
    "                return True\n",
    "            if dfs(idx+1, sumOfN - nums[idx], N-1):\n",
    "                return True\n",
    "            return False \n",
    "        \n",
    "        for cnt in range(1, len(nums)):\n",
    "            if S*cnt % n != 0: continue\n",
    "            if dfs(0, S*cnt//n, cnt):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\r\n",
    "        # BUG 枚举A数组长度 变为子集和问题 \r\n",
    "        # 事实上A， B是对称的 也就是说只需要枚举到 15\r\n",
    "        # dp[i][k][m] 表示 前i个数中选择k个数和为m的可行性 \r\n",
    "        n = len(nums)\r\n",
    "        s = sum(nums)\r\n",
    "        @cache\r\n",
    "        def dfs(i, k, m):\r\n",
    "            if i < k:\r\n",
    "                return False\r\n",
    "            if i == 0:\r\n",
    "                return k == 0 and m == 0\r\n",
    "            if  k == 0:\r\n",
    "                return m == 0\r\n",
    "            res = dfs(i - 1, k, m)\r\n",
    "            if nums[i - 1] <= m:\r\n",
    "                res = dfs(i - 1, k - 1, m - nums[i - 1]) or res \r\n",
    "            return res \r\n",
    "            \r\n",
    "        res = False\r\n",
    "        for i in range(1, n // 2 + 1):\r\n",
    "            # m = s * (i // n) (s * i) 需要被 n 整除 \r\n",
    "            if s * i % n:\r\n",
    "                continue \r\n",
    "            m = s * i // n \r\n",
    "            # print(n, i, m)\r\n",
    "            if dfs(n, i, m):\r\n",
    "                res = True \r\n",
    "                break \r\n",
    "        dfs.cache_clear()\r\n",
    "        return res \r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        # s1+s2=tot,x+y=n,s1*y=s2*x\n",
    "        # (n - x)*s1=(tot - s1)*x=>tot/s1=n/x\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return False\n",
    "        tot = sum(nums)\n",
    "        nums.sort()\n",
    "        @lru_cache(None)\n",
    "        def dfs(i: int, cnt: int, target: int) -> bool:\n",
    "            if i == n:\n",
    "                return target == 0 and cnt == 0\n",
    "            return dfs(i + 1, cnt - 1, target - nums[i]) or dfs(i + 1, cnt, target)\n",
    "        for x in range(1, n):\n",
    "            if tot * x % n == 0:\n",
    "                res = dfs(0, x, tot * x // n)\n",
    "                dfs.cache_clear()\n",
    "                if res:\n",
    "                    return res\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool: \n",
    "        \n",
    "        n = len(nums)\n",
    "        vrg =  mean(nums) \n",
    "        def check(m,su): \n",
    "            @cache\n",
    "            def dfs(target,idx,cnt):\n",
    "                if cnt == 0 and target==0:\n",
    "                    return True\n",
    "                if idx>= n or target < nums[idx]:\n",
    "                    return False \n",
    "                ret = dfs(target-nums[idx],idx+1,cnt-1) \n",
    "                if ret :return True\n",
    "                return dfs( target ,idx+1,cnt) \n",
    "\n",
    "            return dfs(su,0,m)\n",
    "        nums.sort()\n",
    "        step = len(nums) // ( gcd(sum(nums),len(nums)) ) \n",
    "        for m in range( step, len(nums)//2+1, step ):\n",
    "            su = int( vrg * m + 0.5)\n",
    "            # print( m,su )\n",
    "            if check(m,su):return True \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        global n\n",
    "        global flag\n",
    "        flag=0\n",
    "        n=len(nums)\n",
    "        nums=sorted(nums)\n",
    "        if n==1:\n",
    "            return False\n",
    "        if n==2:\n",
    "            if nums[0]!=nums[1]:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        global sum\n",
    "        global average\n",
    "        sum=0\n",
    "        for i in range(n):\n",
    "            sum+=nums[i]\n",
    "        m=n//2\n",
    "        if all(sum * i % n for i in range(1, m + 1)):\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(i,nown,nowsum):\n",
    "            global flag\n",
    "            if flag:\n",
    "                return\n",
    "            if nown>n//2+1:\n",
    "                return\n",
    "            if i==n:\n",
    "                if nown==0:\n",
    "                    return \n",
    "                else:\n",
    "                    if nowsum*n==sum*nown:\n",
    "                        flag=1\n",
    "                        return\n",
    "                    else:\n",
    "                        return \n",
    "            elif nown==0:\n",
    "                dfs(i+1,nown+1,nowsum+nums[i])\n",
    "                dfs(i+1,nown,nowsum)\n",
    "                return \n",
    "            elif nowsum*n>sum*nown:\n",
    "                return\n",
    "            elif nowsum*n==sum*nown:\n",
    "                flag=1\n",
    "                return\n",
    "            else:\n",
    "                dfs(i+1,nown+1,nowsum+nums[i])\n",
    "                dfs(i+1,nown,nowsum)\n",
    "                return \n",
    "        dfs(0,0,0)  \n",
    "        if flag:      \n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        nums=[0]+nums\n",
    "        nums_s=sum(nums)\n",
    "        f=[[set() for __ in range(n+1)] for _ in  range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            f[i][0].add(0)\n",
    "        #print(f)\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,i+1):\n",
    "                if i==n and j==n:continue\n",
    "                f[i][j]=f[i-1][j]|set( x+nums[i] for x in f[i-1][j-1])\n",
    "                #print(i,j,f[i][j])\n",
    "                for x in f[i][j]:\n",
    "                    if x*n==nums_s*j:\n",
    "                        #print(\"----\",i,j,f[i][j])\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        if len(nums) <= 1:\n",
    "            return False\n",
    "        self.n = len(nums)\n",
    "        s = sum(nums)\n",
    "        nums = [num * self.n - s for num in nums]\n",
    "        if 0 in nums:\n",
    "            return True\n",
    "        self.low = [n for n in nums if n < 0]\n",
    "        self.high = [n for n in nums if n > 0]\n",
    "        self.len_low = len(self.low)\n",
    "        self.len_high = len(self.high)\n",
    "        self.d = dict()\n",
    "        return self.b(self.high[0], 1, 0, 1)\n",
    "\n",
    "    def b(self, s, n, i, j):\n",
    "        t = (n, i, j, s)\n",
    "        if t in self.d:\n",
    "            return self.d[t]\n",
    "        if s == 0:\n",
    "            r = n < self.n\n",
    "        elif s > 0:\n",
    "            r = i < self.len_low and (self.b(s + self.low[i], n + 1, i + 1, j) or self.b(s, n, i + 1, j))\n",
    "        else:\n",
    "            r = j < self.len_high and (self.b(s + self.high[j], n + 1, i, j + 1) or self.b(s, n, i, j + 1))\n",
    "        self.d[t] = r\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        if len(nums) <= 1:\n",
    "            return False\n",
    "\n",
    "        all = sum(nums)\n",
    "        self.n = len(nums)\n",
    "\n",
    "        nums = [num * self.n - all for num in nums]\n",
    "        if 0 in nums:\n",
    "            return True\n",
    "\n",
    "        self.low = [n for n in nums if n < 0]\n",
    "        self.high = [n for n in nums if n > 0 ]\n",
    "        self.len_low = len(self.low)\n",
    "        self.len_high = len(self.high)\n",
    "\n",
    "        self.d = dict()\n",
    "        return self.b(self.high[0], 1, 0, 1)\n",
    "\n",
    "    def b(self, s, n, i ,j):\n",
    "        t = (n, i, j, s)\n",
    "        if t in self.d:\n",
    "            return self.d[t]\n",
    "        if s == 0:\n",
    "            r = n < self.n\n",
    "        elif s > 0:\n",
    "            r = i < self.len_low and (self.b(s + self.low[i], n + 1, i + 1, j) or self.b(s, n, i + 1, j))\n",
    "        else:\n",
    "            r = j < self.len_high and (self.b(s + self.high[j], n + 1, i, j + 1) or self.b(s, n, i, j + 1))\n",
    "        self.d[t] = r\n",
    "        return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        nums.sort(reverse=True)\n",
    "        #print(nums)\n",
    "        cn = Counter(nums[1:])\n",
    "        keys = sorted(cn.keys())\n",
    "        #print(keys)\n",
    "        @cache\n",
    "        def dfs(i, t, c):\n",
    "            if i == len(cn):\n",
    "                if c != n and t * n == c  * s:\n",
    "                    return True\n",
    "                return False\n",
    "\n",
    "            if t * n == c * s:\n",
    "                return True\n",
    "            if t * n > c * s and keys[i] > t // c:\n",
    "                return False\n",
    "            \n",
    "            for j in range(cn[keys[i]] + 1):\n",
    "                if dfs(i+1, t + j * keys[i], c+j):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        t = dfs(0, nums[0], 1)\n",
    "        dfs.cache_clear()\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        S = sum(nums)\n",
    "        n = len(nums)\n",
    "        if S == 0:\n",
    "            return n > 1\n",
    "        # total/n == sum/cnt\n",
    "        # => total*cnt/n = sum\n",
    "        nums.sort(key=lambda x: -x)\n",
    "        @cache\n",
    "        def dfs(idx: int, sumOfN: int, N: int) -> bool:\n",
    "            if sumOfN < 0:\n",
    "                return False\n",
    "            if sumOfN == 0 and N == 0:\n",
    "                return True\n",
    "            if N == 0:\n",
    "                return sumOfN == 0\n",
    "            if idx == n:\n",
    "                return False\n",
    "            if dfs(idx+1, sumOfN, N):\n",
    "                return True\n",
    "            if dfs(idx+1, sumOfN - nums[idx], N-1):\n",
    "                return True\n",
    "            return False \n",
    "        \n",
    "        for cnt in range(1, len(nums)):\n",
    "            if S*cnt % n != 0: continue\n",
    "            if dfs(0, S*cnt//n, cnt):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArraySameAverage(self, nums: List[int]) -> bool:\n",
    "        total = sum(nums)\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return False \n",
    "        avgnum = total/n\n",
    "        nums.sort()\n",
    "        dic = defaultdict(int)\n",
    "        maxcnt = 0\n",
    "        for i in range(1,n):\n",
    "            if total*i%n == 0:\n",
    "                dic[i] = total*i//n \n",
    "                maxcnt = max(maxcnt,i)\n",
    "        if maxcnt == 0:\n",
    "            return False \n",
    "        @cache\n",
    "        def dfs(idx,cnt,s):\n",
    "           # if cnt>maxcnt:\n",
    "            #    return False \n",
    "            if cnt in dic:\n",
    "                if s == dic[cnt]:\n",
    "                    return True \n",
    "                if s>dic[cnt]:\n",
    "                    return False \n",
    "            if idx == n:\n",
    "                return False \n",
    "            if dfs(idx+1,cnt+1,s+nums[idx]):\n",
    "                return True\n",
    "            if dfs(idx+1,cnt,s):\n",
    "                return True\n",
    "            return False\n",
    "        return dfs(0,0,0)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\r\n",
    "#     @cache\r\n",
    "#     def splitArraySameAverage(self, nums) -> bool:\r\n",
    "#         avg = sum(nums) / len(nums)\r\n",
    "#         @cache\r\n",
    "#         def func(n, s):\r\n",
    "\r\n",
    "#             if func(n-1, s):\r\n",
    "#                 return True\r\n",
    "#             else:\r\n",
    "#                 for i in range(0, len(nums)):\r\n",
    "#                     if func(n-1, s-nums[i]):\r\n",
    "#                         return True\r\n",
    "#             return False\r\n",
    "import time\r\n",
    "class Solution:\r\n",
    "    def splitArraySameAverage(self, nums) -> bool:\r\n",
    "        n = len(nums)\r\n",
    "        m = n // 2\r\n",
    "        s = sum(nums)\r\n",
    "        # if all(s * i % n for i in range(1, m + 1)):\r\n",
    "        #     return False\r\n",
    "        \r\n",
    "        @cache\r\n",
    "        def func(k, tmp_s):\r\n",
    "            # if i > m:\r\n",
    "            #     return False\r\n",
    "            # if i > 0 and i * s == tmp_s * n:\r\n",
    "            #     return True\r\n",
    "            # if k == n:\r\n",
    "            #     return False\r\n",
    "            if k == 0:\r\n",
    "                ans = 0\r\n",
    "                if tmp_s == nums[0]:\r\n",
    "                    ans += 2\r\n",
    "                if tmp_s == 0:\r\n",
    "                    ans += 1\r\n",
    "                return ans\r\n",
    "\r\n",
    "            return (func(k-1, tmp_s-nums[k]) << 1) | (func(k-1, tmp_s))  \r\n",
    "        time.sleep(0.01)\r\n",
    "        for i in range(1, m+1):\r\n",
    "            if (s*i%n == 0): \r\n",
    "                if func(n-1, s*i/n) & 1<<i:\r\n",
    "                    return True\r\n",
    "    \r\n",
    "        return False\r\n",
    "        \r\n",
    "    \r\n",
    "#             return False\r\n",
    "\r\n",
    "        # dp = [set() for _ in range(m + 1)]\r\n",
    "        # dp[0].add(0)\r\n",
    "        # for num in nums:\r\n",
    "        #     for i in range(m, 0, -1):\r\n",
    "        #         for x in dp[i - 1]:\r\n",
    "        #             curr = x + num\r\n",
    "        #             if curr * n == s * i:\r\n",
    "        #                 return True\r\n",
    "        #             dp[i].add(curr)\r\n",
    "        # return False\r\n",
    "\r\n",
    "print(Solution().splitArraySameAverage([0,2,9,0,9,0,0,2,0,3]))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
